A Physical Unclonable Function (PUF) is a function which is embodied as a physical system, in such a way that an output of the function for an input is obtained by offering the input to the physical system in the form of a stimulus, and mapping the behavior that occurs as a result of an interaction between the stimulus and the physical system to an output. Wherein the interaction is unpredictable and depends on essentially random elements in the physical system, to such an extent, that it is unfeasible to obtain the output, without having had physical access to the physical system, and that it is unfeasible to reproduce the physical system. Preferably, a PUF is also easy to evaluate. For practical uses, PUFs are preferably low in manufacture costs.
Conventionally, an input or stimulus that a PUF accepts is called a ‘challenge’. The output of a PUF, that is, the behavior the PUF exhibits after interaction with the stimulus, is called a ‘response’. A pair comprising a challenge and the corresponding response of a PUF is called a challenge-response pair. Some types of PUFs allow a wide range of different inputs, some types allow a more limited range of inputs, or may even allow only a single input. Challenging a PUF with some single challenge may also be called an ‘activation’ of the PUF.
It would be most preferable, if a PUF when evaluated multiple times for the same challenge would produce multiple responses which are all equal. This property is not necessary though, and, in practice, most PUFs do not posses it. As long as the multiple responses lie sufficiently close to each other, the PUF can be usefully applied.
Since the interaction between a stimulus and the physical system cannot be predicted without access to the system, the PUF is hard to characterize and to model. The output of a particular PUF for an input can therefore only be obtained using the particular physical system underlying the particular PUF. Possession of a challenge-response pair is proof that at some point the challenge was offered to the unique physical system that underlies the PUF. Because of this property, i.e., the property that challenge-response pairs are coupled to a unique physical device, a PUF is called unclonable. By equipping a device with a PUF, the device also becomes unclonable.
Physical systems that are produced by a production process that is, at least in part, uncontrollable, i.e., a production process which will inevitably introduce some randomness, turn out to be good candidates for PUFs.
One advantage of PUFs is that they inherently possess tamper resistant qualities: disassembling the PUF to observe its working, will also disturb the random elements and therefore also disturb the way inputs are mapped to outputs. Various types of PUFs are known in the art, including various types of electronic PUFs, including various types of PUFs based on electronic memories. PUFs may also be based on other concepts, e.g., optical PUFs.
One way of constructing a PUF uses a static random access memory (SRAM); these PUFs are called SRAM PUFs. SRAMs have the property that after they are powered-up, they are filled with a random pattern of on-bits and off-bits. Although the pattern may not repeat itself exactly if the SRAM is powered-up a next time, the differences between two such patterns is typically much smaller than half the number of bits in the state.
A second kind of S-RAM PUFs is constructed with Dual Port RAM. By writing at the same time different information on both ports, i.e., challenging the RAM with the different information, the memory cell is brought into an undefined state, which shows a PUF-like behavior.
Due to unavoidable variations during production, the configuration of the components of an SRAM relative to each other is at least slightly random. These variations are reflected, e.g., in a slightly different threshold voltage of the transistors in the memory cells of the SRAM. When the SRAM is read out in an undefined state, e.g., before a write action, the output of the SRAM depends on the random configuration. Producing a new SRAM, with the same characteristic behavior requires producing an SRAM with the same configuration, a configuration which was achieved randomly. As this is unfeasible, the SRAM is unclonable as a physical system, that is, it is a PUF.
A further example of PUFs is the so-called Butterfly PUF. The Butterfly PUF comprises a plurality of butterfly PUF cells. A butterfly PUF cells comprises a cross-coupling of two latches or flip-flops. The butterfly PUF can be implemented on a Field Programmable Gate Array (FPGA), even if the FPGA does not comprise SRAM. The butterfly PUF cell can be viewed as a simulation of an SRAM memory cell using elements that are available on an FPGA. The way a butterfly operates is also similar to that of the SRAM. The butterfly PUF is also able to extract secrets from the complex physical characteristics of the integrated circuits on which it is implemented. Butterfly PUFs are explained more fully in the following paper: Sandeep S. Kumar, Jorge Guajardo, Roel Maes, Geert-Jan Schrijen, Pim Tuyls, “The butterfly PUF protecting IP on every FPGA,”, pp. 67-70, 2008 IEEE International Workshop on Hardware-Oriented Security and Trust, 2008. The butterfly PUF is also described in the international patent application “identification of devices using physically unclonable functions”, published as WO2009/024913, and incorporated herein by reference. See in particular FIGS. 8 and 10, and the corresponding description.
One application of PUFs is to derive a cryptographic key on an electronic circuit. The electronic circuit typically includes an integrated Circuit (IC) and/or programmable logic. The programmable logic comprises, e.g., a field-programmable gate array (FPGA), a programmable logic device (PLD), or a digital signal processor (DSP), a microprocessor, etc. Instead of storing the cryptographic key in a non-volatile memory of some kind, the key is generated from the PUF only when the key is needed by the device. The key can be deleted when it is no longer needed. The next time the key is needed, it can be derived again from the PUF. Since the PUF may not give the exact same result when the same challenge is evaluated twice, a so-called Helper Data algorithm, also known as a Fuzzy Extractor, may be used to ensure that the key will be the same, each time it is derived. One way of using helper data to construct reproducible values from noisy measurements is described, e.g., in international patent application WO 2006/129242, “Template Renewal in Helper Data Systems”, which is included herein by reference.
One way to use a PUF to create a cryptographic key is as follows. First, during an enrollment phase, a challenge-response pair is created. Then, using the fuzzy extractor, helper data is created. On the device, the challenge and the helper data are stored in a non-volatile memory. To derive the cryptographic key, a new response is obtained by evaluating the PUF for the challenge again. By combining the new response with the stored helper data, according to a helper data algorithm, a key is derived. The helper data ensures that the key is the same, each time it is derived.
Without a PUF, the cryptographic key may be recovered by an attacker, by mounting a physical attack on the non-volatile memory where the key is traditionally stored. For example, the attacker may open the memory and probe its content. Using a PUF makes this type of attack much harder, since the sought PUF pattern only materializes when the PUF is activated. Moreover, opening the PUF will typically disturb the precise way in which the PUF interacts with inputs. Accordingly, information the attacker learns from his probe is not related to the interaction which was used to create the cryptographic key. This makes it harder for an attacker to find the key using a physical attack.
In other words, and attacker cannot intrusively open a chip comprising a PUF since he needs the chip to function in order for the PUF pattern to materialize and because opening the chip would destroy the capability of the PUF to produce the PUF pattern, on the other hand he must open the chip since otherwise he has no way of accessing the secret PUF pattern.
Unfortunately, there may be a way out of this dilemma for the attacker. Freezing a PUF based on an electronic memory after is has been activated may cause a PUF pattern to become temporarily fixed in the memory, even if the chip is deactivated and opened. The pattern becomes, as it were, frozen in the memory. After freezing the memory, an attacker can take the chip apart and determine what its memory content was at the time of freezing. Similar attacks are discussed in the paper: Halderman, A. J., S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten (2009). Lest we remember: cold-boot attacks on encryption keys. Commun. ACM 52 (5), 91-98.
Examining a memory, after it has been frozen may be possible by extracting the memory from the system and reading out its contents in a different system. A countermeasure against this attack is to integrate the memory that is used as PUF in the system, instead of using a separate memory device, which may be extracted from the system separately. Even in the latter case, where the memory is an integrated part of the system, its content while frozen may be examined by opening the chip and looking at the inside using an electron microscope.
Freezing a memory may be done by such low-teach means as spraying the memory chip with an upside-down canister of multipurpose duster spray, also known as ‘canned air’. Holding the can upside down will produce the required low temperatures. A more advanced technique is to apply liquid nitrogen to the memory chip. The latter procedure is found to produce even better results, i.e., more memory cells retain the value they had during operation before the freezing.
It is noted that a memory may be vulnerable to illicit access without freezing, for example, by probing a bus to the memory using thin micro-probes or needles that are stitched into a bus line. Nevertheless, we will collectively refer to all types of attack in which illicit access may be obtained to the content of a memory during its operational use, as a freezing attack.
It is a problem of the prior art that a PUF based on an electronic memory may be vulnerable to a freezing attack.